5.2.2. Karmaşıklık (Complexity)

Karmaşıklık bir algoritmanın çok sayıda parametre karşısında maliyet davranışındaki değişikliği/artmayı gösteren kavramsal bir ifadedir. Genel olarak, az sayıda parametreler için karmaşıklıkla ilgilenilmez; eleman sayısı n'nin sonsuza gitmesi durumunda algoritmanın maliyet hesabının davranışını görmek veya diğer benzer işleri yapan algoritmalarla karşılaştırmak için kullanılır.

Programların karmaşıklığını matemetiksel olarak değişebilir.

Karmaşıklığı ifade edebilmek için asimtotik ifadeler kullanılmaktadır; bu amaçla O(g(n)), (g(n)), (g(n)), o(g(n)) gibi tanımlara başvurulur. Genel olarak büyük O ve q notasyonları daha çok kullanılmaktadır. Örneğin, bir sıralama algoritmasının karmaşıklığı O(n²) ise, bunun anlamı, n çok büyük değerlere giderken algoritmanın zaman maliyeti karesel olarak artar şeklindedir. Örneğin karmaşıklığı O(nlog₂n) olan bir sıralama algoritması O(n²) olana göre daha iyidir; n çok büyük değerlere giderken karmaşıklık doğrusal çarpanlı logaritmik olarak artar. Aslında, bulunabilse, en iyi çözümü veren karmaşıklık O(1) şeklinde sabit olanıdır; ancak asosiyatif bellek¹ veya çok iyi bir çırpı fonksiyonu bulunmadıkça bu durum çoğu zaman sağlanmaz.